|
In number theory, Proth's theorem is a primality test for Proth numbers. It states that if ''p'' is a Proth number, of the form ''k''2''n'' + 1 with ''k'' odd and ''k'' < 2''n'', and if there exists an integer ''a'' for which : then ''p'' is prime. In this case ''p'' is called a Proth prime. This is a practical test because if ''p'' is prime, any chosen ''a'' has about a 50 percent chance of working. If ''a'' is a quadratic nonresidue modulo ''p'' then the converse is also true, and the test is conclusive. Such an ''a'' may be found by iterating ''a'' over small primes and computing the Jacobi symbol until: :: Thus, in contrast to many Monte Carlo primality tests (randomized algorithms that can return a false positive), the primality testing algorithm based on Proth's theorem is a Las Vegas algorithm, always returning the correct answer but with a running time that varies randomly. ==Numerical examples== Examples of the theorem include: * for ''p'' = 3, 21 + 1 = 3 is divisible by 3, so 3 is prime. * for ''p'' = 5, 32 + 1 = 10 is divisible by 5, so 5 is prime. * for ''p'' = 13, 56 + 1 = 15626 is divisible by 13, so 13 is prime. * for ''p'' = 9, which is not prime, there is no ''a'' such that ''a''4 + 1 is divisible by 9. The first Proth primes are : :3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 …. , the largest known Proth prime is 19249 · 213018586 + 1, found by Seventeen or Bust. It has 3,918,990 digits and is the largest known prime which is not a Mersenne prime. 〔http://primes.utm.edu/top20/page.php?id=3〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Proth's theorem」の詳細全文を読む スポンサード リンク
|